import java.util.ArrayList;

import java.util.List;

/**
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 示例:
 * <p>
 * 输入: nums = [1,2,3]
 * 输出:
 * [
 * [3],
 *   [1],
 *   [2],
 *   [1,2,3],
 *   [1,3],
 *   [2,3],
 *   [1,2],
 *   []
 * ]
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}).size());
    }

    public static List<List<Integer>> all;

    public static List<List<Integer>> subsets(int[] nums) {
        all = new ArrayList<List<Integer>>();
        all.add(new ArrayList<Integer>());
        for (int i = 0; i < nums.length; i++) {
            subsets(nums, i);
        }
        return all;
    }

    /**
     * 从num里面选第i个添加到结果中
     *
     * @param nums
     * @param i
     */
    public static void subsets(int[] nums, int i) {
        int size = all.size();
        List<Integer> newList;
        for (int j = 0; j < size; j++) {
            newList = new ArrayList<Integer>(all.get(j));
            newList.add(nums[i]);
            all.add(newList);
        }
    }

}